package 中等.动态规划.子序列;

/**
 * 给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
 * 环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是
 * nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
 * 子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i],
 * nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-sum-circular-subarray
 */
public class 环形子数组的最大和_918 {

    public static void main(String[] args) {

        // 1 1 -1 2
        System.out.println(maxSubarraySumCircular2(new int[]{3, -1, 2, -1}));

        System.out.println(maxSubarraySumCircular3(new int[]{-3, -2, -3}));

    }

    /**
     * 贪心+模拟
     * 计算每个以 i 开头的环形数组和最大值，如果
     * 从 i 遍历到 j 的和 sum < 0，那么下次 i 从
     * j+1的位置开始统计
     *
     * @param nums
     * @return
     */
    public static int maxSubarraySumCircular(int[] nums) {
        int max = nums[0];

        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < i + nums.length; j++) {
                sum += nums[j % nums.length];
                max = Math.max(max, sum);

                if (sum <= 0) {
                    i = j;
                    break;
                }
            }
        }
        return max;
    }

    /**
     * 动态规划+分类讨论
     * 1，最大和存在于首尾两端
     * 可以看作从首部选取以 nums[0] 开头的子序列 + 以 nums[n-1] 结尾的子序列
     * 最大和为多少
     * 子问题：
     * // 代表 [0,i] 中以 0 开头的连续子序列和最大为多少
     * int[] prefixDp = new int[n];
     * // 代表 [i,n-1] 中以 n-1 结尾的连续子序列和最大为多少
     * int[] suffixDp = new int[n];
     * 状态转移方程：
     * max = Math.max(max, prefixDp[i] + suffixDp[i + 1])
     * <p>
     * 2，最大和存在于数组中间
     * 子问题：
     * 以 nums[i] 结尾的最大子序列和为多少
     * 状态转移方程：
     * 如果 dp[i-1] < 0 ，那么最大和即为 nums[i] 一个数
     * 否则 dp[i] = dp[i-1] + nums[i]
     */
    public static int maxSubarraySumCircular2(int[] nums) {
        int n = nums.length;
        // 代表 [0,i] 中以 0 开头的连续子序列和最大为多少
        int[] prefixDp = new int[n];
        // 代表 [i,n-1] 中以 n-1 结尾的连续子序列和最大为多少
        int[] suffixDp = new int[n];
        prefixDp[0] = nums[0];
        suffixDp[n - 1] = nums[n - 1];

        int prefixSum = nums[0], suffixSum = nums[n - 1];
        for (int i = 1; i < n; i++) {
            prefixSum += nums[i];
            suffixSum += nums[n - 1 - i];

            prefixDp[i] = Math.max(prefixDp[i - 1], prefixSum);
            suffixDp[n - 1 - i] = Math.max(suffixDp[n - i], suffixSum);
        }

        int max = prefixDp[n - 1];
        for (int i = 0; i < n - 1; i++) {
            max = Math.max(max, prefixDp[i] + suffixDp[i + 1]);
        }

        int preSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (preSum < 0) {
                preSum = nums[i];
            } else {
                preSum += nums[i];
            }

            max = Math.max(max, preSum);
        }
        return max;
    }

    /**
     * 动态规划+逆向思维
     * 1，最大和存在于首尾两端
     * 这种情况可以看作 在数组中间选择最小连续子序列和 为多少
     * totalSum - minSum = maxSum
     */
    public static int maxSubarraySumCircular3(int[] nums) {
        int max = nums[0];
        int totalSum = nums[0];
        int preSum = nums[0];
        // 答案在中间的情况
        for (int i = 1; i < nums.length; i++) {
            if (preSum < 0) {
                preSum = nums[i];
            } else {
                preSum += nums[i];
            }
            max = Math.max(max, preSum);

            totalSum += nums[i];
        }
        // 答案在两端的情况
        preSum = 0;
        for (int i = 1; i < nums.length - 1; i++) {
            if (preSum > 0) {
                preSum = nums[i];
            } else {
                preSum += nums[i];
            }

            max = Math.max(max, totalSum - preSum);
        }
        return max;
    }

}
